package ljl.alg.jianzhioffer.round2;

import java.util.LinkedList;
import java.util.TreeMap;

public class _59_1_max_sliding_window_number {
    
    // 队列放数字，map 放次数，记录最大值？
    // 数字出去时记录变化
    /**
     * 怎么还是不会滑动窗口啊
     * 擦
     * 擦
     *
     * 很好，发现了不足，这是好事
     *
     * 我这个解法不是滑动窗口！！！！
     * */
    public int[] maxSlidingWindow_sb(int[] nums, int k) {
        TreeMap<Integer, Integer> dic = new TreeMap<>();
        LinkedList<Integer> q = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            dic.put(nums[i], dic.getOrDefault(nums[i], 0) + 1);
            q.add(nums[i]);
        }
        int[] res = new int[nums.length - k + 1];
        res[0] = dic.lastEntry().getKey();
        for (int i = k, j = 1; i < nums.length; i++) {
            q.add(nums[i]);
            dic.put(nums[i], dic.getOrDefault(nums[i], 0) + 1);
            Integer poll = q.poll();
            int count = dic.get(poll);
            if (count == 1) {
                dic.remove(poll);
            } else {
                dic.put(poll, count - 1);
            }
            res[j++] = dic.lastEntry().getKey();
        }
        return res;
    }
    
    /**
     * 路飞答案
     * */
    public int[] maxSlidingWindow_lufei(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        LinkedList<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        // 未形成窗口
        // 原来是单调队列！大数在左边，
        // 因为啥呢？因为小数出了窗口，对最大值没影响，所以只关注大数就行了
        // 大数左边的小数全都出队
        for(int i = 0; i < k; i++) {
            // 大数进队之前要把比它小的全挤出去，形成这么一个递减的队列
            // 可以看到，不会把相等的挤出去，只挤出去小的
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
        }
        res[0] = deque.peekFirst();
        // 形成窗口后
        for(int i = k; i < nums.length; i++) {
            // 先把第一个数挤出去，如果第一个数，它恰好，是队列里的大数，就出队
            if(deque.peekFirst() == nums[i - k])
                deque.removeFirst();
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
            res[i - k + 1] = deque.peekFirst();
        }
        return res;
    }
    
    /**
     * 我再进行抄写
     * 还行，背过了
     * 但是明天，我未必会做！
     * */
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        LinkedList<Integer> q = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!q.isEmpty() && q.peekLast() < nums[i]) {
                q.pollLast();
            }
            q.offer(nums[i]);
        }
        int[] res = new int[nums.length - k + 1];
        res[0] = q.peekFirst();
        for (int i = k, j = 1; i < nums.length; i++) {
            if (nums[i - k] == q.peekFirst())
                q.poll();
            while (!q.isEmpty() && q.peekLast() < nums[i])
                q.pollLast();
            q.offer(nums[i]);
            res[j++] = q.peekFirst();
        }
        return res;
    }
    
}
